﻿using System;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;


namespace Algoritmia.Problems.Geometry.ConvexMin
{
    public class ConvexMinFinder<T> : IConvexSequenceMinFinder<T>
    {
        private readonly Comparison<T> _comparison;

        public ConvexMinFinder(Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
        }

        #region Implementation of IConvexSequenceMinFinder<T>

        public T Min(Lists.IList<T> list)
        {
            Func<int, int, T> f = null;
            f = (start, end) =>
                    {
                        if (end - start > 2)
                        {
                            var middle = (start + end)/2;
                            if (_comparison(list[middle - 1], list[middle]) > 0)
                            {
                                return f(middle, end);
                            }
                            return f(start, middle);
                        }
                        if (end - start == 2)
                        {
                            return _comparison(list[start], list[start + 1]) < 0 ? list[start] : list[start + 1];
                        }
                        if (end - start == 1)
                        {
                            return list[start];
                        }

                        throw new InvalidOperationException(
                            "Is not possible to find the minimum element of an empty sequence");
                    };

            return f(0, list.Count);
        }

        #endregion
    }
}
